package com.shm.leetcode;

import java.util.Arrays;

/**
 * @author: shm
 * @dateTime: 2020/10/7 9:01
 * @description: 75. 颜色分类
 * 给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
 * <p>
 * 此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
 * <p>
 * 注意:
 * 不能使用代码库中的排序函数来解决这道题。
 * <p>
 * 示例:
 * <p>
 * 输入: [2,0,2,1,1,0]
 * 输出: [0,0,1,1,2,2]
 * 进阶：
 * <p>
 * 一个直观的解决方案是使用计数排序的两趟扫描算法。
 * 首先，迭代计算出0、1 和 2 元素的个数，然后按照0、1、2的排序，重写当前数组。
 * 你能想出一个仅使用常数空间的一趟扫描算法吗？
 */
public class SortColors {
    public void sortColors(int[] nums) {
        Arrays.sort(nums);
    }

    public void sortColors_2(int[] nums) {
        int[] colors = new int[3];
        for (int num : nums) {
            colors[num]++;
        }

        int i = 0;
        for (int j = 0; j < colors.length; j++) {
            for (int k = 0; k < colors[j]; k++) {
                nums[i] = j;
                i++;
            }
        }
    }

    /**
     * @author: shm
     * @dateTime: 2020/10/7 10:15
     * @description: 方法三：双指针
     * 思路与算法
     * <p>
     * 与方法二类似，我们也可以考虑使用指针 p_0p
     * 0
     * ​
     * 来交换 00，p_2p
     * 2
     * ​
     * 来交换 22。此时，p_0p
     * 0
     * ​
     * 的初始值仍然为 00，而 p_2p
     * 2
     * ​
     * 的初始值为 n-1n−1。在遍历的过程中，我们需要找出所有的 00 交换至数组的头部，并且找出所有的 22 交换至数组的尾部。
     * <p>
     * 由于此时其中一个指针 p_2p
     * 2
     * ​
     * 是从右向左移动的，因此当我们在从左向右遍历整个数组时，如果遍历到的位置超过了 p_2p
     * 2
     * ​
     * ，那么就可以直接停止遍历了。
     * <p>
     * 具体地，我们从左向右遍历整个数组，设当前遍历到的位置为 ii，对应的元素为 \textit{nums}[i]nums[i]；
     * <p>
     * 如果找到了 00，那么与前面两种方法类似，将其与 \textit{nums}[p_0]nums[p
     * 0
     * ​
     * ] 进行交换，并将 p_0p
     * 0
     * ​
     * 向后移动一个位置；
     * <p>
     * 如果找到了 22，那么将其与 \textit{nums}[p_2]nums[p
     * 2
     * ​
     * ] 进行交换，并将 p_2p
     * 2
     * ​
     * 向前移动一个位置。
     * <p>
     * 这样做是正确的吗？可以发现，对于第二种情况，当我们将 \textit{nums}[i]nums[i] 与 \textit{nums}[p_2]nums[p
     * 2
     * ​
     * ] 进行交换之后，新的 \textit{nums}[i]nums[i] 可能仍然是 22，也可能是 00。然而此时我们已经结束了交换，开始遍历下一个元素 \textit{nums}[i+1]nums[i+1]，不会再考虑 \textit{nums}[i]nums[i] 了，这样我们就会得到错误的答案。
     * <p>
     * 因此，当我们找到 22 时，我们需要不断地将其与 \textit{nums}[p_2]nums[p
     * 2
     * ​
     * ] 进行交换，直到新的 \textit{nums}[i]nums[i] 不为 22。此时，如果 \textit{nums}[i]nums[i] 为 00，那么对应着第一种情况；如果 \textit{nums}[i]nums[i] 为 11，那么就不需要进行任何后续的操作。
     * <p>
     * 复杂度分析
     * <p>
     * 时间复杂度：O(n)O(n)，其中 nn 是数组 \textit{nums}nums 的长度。
     * <p>
     * 空间复杂度：O(1)O(1)。
     * <p>
     * 作者：LeetCode-Solution
     * 链接：https://leetcode-cn.com/problems/sort-colors/solution/yan-se-fen-lei-by-leetcode-solution/
     */
    public void sortColors_4(int[] nums) {
        int n = nums.length;
        int left = 0;
        int right = n - 1;
        for (int i = 0; i <= right; i++) {
            while (i <= right && nums[i] == 2) {
                int tmp = nums[i];
                nums[i] = nums[right];
                nums[right] = tmp;
                right--;
            }
            if (nums[i] == 0) {
                int tmp = nums[i];
                nums[i] = nums[left];
                nums[left] = tmp;
                left++;
            }
        }
    }

    /**
     * @author: shm
     * @dateTime: 2020/10/7 10:14
     * @description: 前言
     * 本题是经典的「荷兰国旗问题」，由计算机科学家 Edsger W. Dijkstra 首先提出。
     * <p>
     * 根据题目中的提示，我们可以统计出数组中 0, 1, 20,1,2 的个数，再根据它们的数量，重写整个数组。这种方法较为简单，也很容易想到，而本题解中会介绍两种基于指针进行交换的方法。
     * <p>
     * 方法一：单指针
     * 思路与算法
     * <p>
     * 我们可以考虑对数组进行两次遍历。在第一次遍历中，我们将数组中所有的 00 交换到数组的头部。在第二次遍历中，我们将数组中所有的 11 交换到头部的 00 之后。此时，所有的 22 都出现在数组的尾部，这样我们就完成了排序。
     * <p>
     * 具体地，我们使用一个指针 \textit{ptr}ptr 表示「头部」的范围，\textit{ptr}ptr 中存储了一个整数，表示数组 \textit{nums}nums 从位置 00 到位置 \textit{ptr}-1ptr−1 都属于「头部」。\textit{ptr}ptr 的初始值为 00，表示还没有数处于「头部」。
     * <p>
     * 在第一次遍历中，我们从左向右遍历整个数组，如果找到了 00，那么就需要将 00 与「头部」位置的元素进行交换，并将「头部」向后扩充一个位置。在遍历结束之后，所有的 00 都被交换到「头部」的范围，并且「头部」只包含 00。
     * <p>
     * 在第二次遍历中，我们从「头部」开始，从左向右遍历整个数组，如果找到了 11，那么就需要将 11 与「头部」位置的元素进行交换，并将「头部」向后扩充一个位置。在遍历结束之后，所有的 11 都被交换到「头部」的范围，并且都在 00 之后，此时 22 只出现在「头部」之外的位置，因此排序完成。
     * <p>
     * <p>
     * 复杂度分析
     * <p>
     * 时间复杂度：O(n)O(n)，其中 nn 是数组 \textit{nums}nums 的长度。
     * <p>
     * 空间复杂度：O(1)O(1)。
     * <p>
     * 作者：LeetCode-Solution
     * 链接：https://leetcode-cn.com/problems/sort-colors/solution/yan-se-fen-lei-by-leetcode-solution/
     */
    public void sortColors_5(int[] nums) {
        int n = nums.length;
        int left = 0;
        for (int i = 0; i < n; i++) {
            if (nums[i] == 0) {
                int tmp = nums[i];
                nums[i] = nums[left];
                nums[left] = tmp;
                left++;
            }
        }

        for (int i = 0; i < n; i++) {
            if (nums[i] == 1) {
                int tmp = nums[i];
                nums[i] = nums[left];
                nums[left] = tmp;
                left++;
            }
        }
    }


    /**
     * @author: shm
     * @dateTime: 2020/10/7 10:44
     * @description: 循环不变量定义 1
     * 循环不变量：声明的变量在遍历的过程中需要保持定义不变。
     * <p>
     * 设计循环不变量的原则
     * 说明：设计循环不变量的原则是 不重不漏。
     * <p>
     * len 是数组的长度；
     * 变量 zero 是前两个子区间的分界点，一个是闭区间，另一个就必须是开区间；
     * 变量 i 是循环变量，一般设置为开区间，表示 i 之前的元素是遍历过的；
     * two 是另一个分界线，我设计成闭区间。
     * 如果循环不变量定义如下：
     * <p>
     * 所有在子区间 [0, zero) 的元素都等于 0；
     * 所有在子区间 [zero, i) 的元素都等于 1；
     * 所有在子区间 [two, len - 1] 的元素都等于 2。
     * 于是编码要解决以下三个问题：
     * <p>
     * 变量初始化应该如何定义；
     * 在遍历的时候，是先加减还是先交换；
     * 什么时候循环终止。
     * 处理这三个问题，完全看循环不变量的定义。
     * <p>
     * 编码的时候，zero 和 two 初始化的值就应该保证上面的三个子区间全为空；
     * 在遍历的过程中，「下标先加减再交换」、还是「先交换再加减」就看初始化的时候变量在哪里；
     * 退出循环的条件也看上面定义的循环不变量，在 i == two 成立的时候，上面的三个子区间就正好 不重不漏 地覆盖了整个数组，并且给出的性质成立，题目的任务也就完成了。
     * <p>
     * 复杂度分析：
     * <p>
     * 时间复杂度：O(N)O(N)，这里 NN 是输入数组的长度；
     * 空间复杂度：O(1)O(1)。
     * <p>
     * 作者：liweiwei1419
     * 链接：https://leetcode-cn.com/problems/sort-colors/solution/kuai-su-pai-xu-partition-guo-cheng-she-ji-xun-huan/
     */
    public void sortColors_6(int[] nums) {
        int len = nums.length;
        if (len < 2) {
            return;
        }

        // all in [0, zero) = 0
        // all in [zero, i) = 1
        // all in [two, len - 1] = 2

        // 循环终止条件是 i == two，那么循环可以继续的条件是 i < two
        // 为了保证初始化的时候 [0, zero) 为空，设置 zero = 0，
        // 所以下面遍历到 0 的时候，先交换，再加
        int zero = 0;

        // 为了保证初始化的时候 [two, len - 1] 为空，设置 two = len
        // 所以下面遍历到 2 的时候，先减，再交换
        int two = len;
        int i = 0;
        // 当 i == two 上面的三个子区间正好覆盖了全部数组
        // 因此，循环可以继续的条件是 i < two
        while (i < two) {
            if (nums[i] == 0) {
                swap(nums, i, zero);
                zero++;
                i++;
            } else if (nums[i] == 1) {
                i++;
            } else {
                two--;
                swap(nums, i, two);
            }
        }
    }

    private void swap(int[] nums, int index1, int index2) {
        int temp = nums[index1];
        nums[index1] = nums[index2];
        nums[index2] = temp;
    }

    /**
     * @author: shm
     * @dateTime: 2020/10/7 10:47
     * @description: 我感觉这个初始化为空没有那么重要， 并不一定需要把范围设置成[0, -1]和[n, n-1]。
     * 初始化成[0,0]和[n-1, n-1]也是可以的，可能的担心是nums[0] nums[n-1]会以错误的值结束。
     * 然而只要数组里面有至少一个0和至少一个2， 它们肯定就会被放到0和n-1位置去。
     */
    public void sortColors_7(int[] nums) {
        int head = 0;
        int i = 0;
        int tail = nums.length - 1;

        while (i <= tail) {
            if (nums[i] == 0) {
                swap(nums, i, head);
                i++;
                head++;
            } else if (nums[i] == 2) {
                swap(nums, i, tail);
                tail--;
            } else if (nums[i] == 1) {
                i++;
            }
        }
    }
}
